When transmission system quality is to be evaluated, it is usual to associate with a certain block of digital signals to be transmitted a digital code obtained by duly processing the signals themselves, and to check whether this code is equal to the code obtained from the block of the received digital signals, processed in the same way as at the transmission. When, however, the correct functioning of an apparatus or a circuit is to be evaluated, a circuit is added for extracting some digital signals from suitable points of the item to be tested and a digital code is computed which is compared with a known code. The comparison results allows the proper functioning or malfunctioning of the item under test to be checked.
A particular kind of such codes, referred to as cyclic redundancy codes or CRD, is obtained as follows. Each block of N digital signals, each of them being associated with a code, is considered as a polynomial of degree N, whose coefficients are the bits of the block itself. This polynomial is divided by a divisor polynomial, having a suitable degree and suitable coefficient values, and the division remainder polynomial coefficients, of degree lower by a unit than that of the divisor, form the cyclic redundancy code of CRC. The higher the remainder polynomial degree, the more accurate the check performed on the data to be tested. Of course, even the complexity of the circuits which perform the division between the polynomials is higher.
The polynomial division, effected by modulus-2 subtractions or additions, i.e. without carry or borrow, generally requires rather complex electronic circuits. However, by exploiting the fact that the data are generally organized into serial blocks and the divisor polynomial is constant and predetermined, the division circuit can be considerably simplified.
A few examples of division circuits, used for generating cyclic codes for error detection, are described in the paper entitled "Cyclic Codes for Error Detection", by W. W. Peterson and D. T. Brown, issued on Proceedings on the IRE, January 1961. They basically consist of a shift register, with a number of stages lower by a unity than the degree of the divisor polynomial, and of modulus-2 adders placed in between the register stages, corresponding to the divisor polynomial terms with coefficients different from zero. Each adder adds the bit coming from the preceding stage of the shift register to the bit entering the division circuit at that instant. The adders are implemented by exclusive-OR gates. As is easy to understand, the division operation is performed by successive shift operations, corresponding to the multiplication of the divisor by the single terms of the quotient, and by modulus-2 additions, corresponding to the successive subtractions of the products obtained from the updated dividend.
Another example of division circuitry wherein the divisor polynomial can be chosen time by time, is described in the paper entitled "Self-Testing by polynomila division" by D. K. Bhavsar and R. W. Heckelman, presented at the International Test Conference, Philadelphia, October 1981. IN this circuit, used for checking the functioning of complex circuits, there are adders at each shift register stage and the signal outgoing from the division circuit is brought to each adder only if the relevant coefficient of the divisor polynomial is different from zero. This higher flexibility of course entails higher circuit complexity.
Moreover, both the solutions examined require a previous operation of reset of the shift register contents whenever the cyclic redundancy code is calculated for a data block, operating in the time interval comprised between the last datum of a block and the first datum of the subsequent block. This operation, in case it is to be performed on the serial flow of data with the relevant clock signals, requires the generation of a reset signal with active phase placed between two successive blanks of the clock signal. It is clear that the generation of such a signal requires rather complex circuits and can cause malfunctionings, especially if the active phase above is not synchronous with the clock signal.